def merge_sort(array, counts):
    if len(array) <= 1:
        return

    m = len(array)//2
    L = array[:m]
    R = array[m:]
    merge_sort(L, counts)
    merge_sort(R, counts)

    i = j = k = 0
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            array[k] = L[i]
            counts[L[i][1]] += j
            i += 1
        else:
            array[k] = R[j]
            j += 1
        k += 1
    while i < len(L):
        array[k] = L[i]
        counts[L[i][1]] += len(R)
        i += 1
        k += 1
    while j < len(R):
        array[k] = R[j]
        j += 1
        k += 1


class Solution(object):
    def countSmaller(self, nums):
        if len(nums) == 0:
            return []
        counts = [0] * len(nums)
        array = [(x, i) for i, x in enumerate(nums)]
        merge_sort(array, counts)
        return counts


print(Solution().countSmaller([5,2,6,1]))
